
// 5.最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        // 使用动态规划来完成
        // dp[i][j] 表示[i , j] 区间是否是回文串
        // dp[i][j] = s[i] == s[j] &&dp[i + 1][j - 1] 

        int n = s.size();
        vector<vector<bool>> dp(n + 1,vector<bool>(n + 1));
        dp[n][n] = true;
        int l = 0 , r = 0;
        for(int i = n - 1; i >= 0 ; i--)
        {
            for(int j = i; j <= n ; j++)
            {
                dp[i][j] = (s[i] == s[j] && ( i == j || i + 1 == j || dp[i + 1][j - 1])); 
                if(j - i + 1 > r - l + 1 && dp[i][j]) r = j , l =i;
            }
        }
        return s.substr(l , r - l + 1);
    }
};